package hot

/*
原题链接:
https://leetcode.cn/problems/subarray-sum-equals-k/

b站 书森学院
560.和为k的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
子数组是数组中元素的连续非空序列。

给你一个整数数组 nums 和一个整数 k, 请你统计并返回 该数组中和为 k的连续子数组的个数.
子数组是数组中元素的连续非空序列.

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

思路:
定义前缀和和数组pre使得 pre[i]为nums[0],...,nums[i]中所有数的和,
即pre[i] = pre[i-1] + nums[i]

那么 [j...i]这个子数组和为k, 这个条件可以转化为 pre[i] - pre[i-1] = k,
简单移项可得符合条件的下标 j需要满足 pre[j-1] == pre[i] - k.
所以我们考虑以 i结尾的和为 k的连续子数组个数时只要统计有多少个前缀和为 pre[i] - k的 pre[j]即可

我们建立哈希表 map, 以前缀和 pre[i]为键, 出现次数和为对应的值, 记录 pre[i]出现的次数,
从左到右, 边更新map 边计算答案, 那么以i结尾的答案 mp[pre[i]-k]即可在 O(1)时间内得到.
最后的答案即为所有下标结尾的和为k的子数组个数之和
*/
func subarraySum(nums []int, k int) int {
	count := 0         //1.声明计数
	pre := 0           //2.声明累加和
	m := map[int]int{} //3.声明map
	m[0] = 1

	for i := 0; i < len(nums); i++ { //4.遍历数组元素
		pre += nums[i]             //4.1累加
		if _, ok := m[pre-k]; ok { //4.2判断map中是否有pre-k, 如果有,那么计数累加
			count += m[pre-k]
		}

		m[pre] += 1 //4.3当前累加数对应的value+1
	}

	return count
}
